#
# Created by Administrator on 2021/7/29 AT 10:18.
#

# 物品编号：1 2 3 4
# 体积：   1 3 5 9
# 价值：   2 3 4 7
# 背包容量：10
# 物品数量无限  这是和0-1背包的唯一区别


def package(m, n, volume, value):
    """
    :param m:  物品个数
    :param n:  背包容量
    :param volume:  每个物品的体积
    :param value:   每个物品的价值
    :return:
    转移方程：  和本行进行对比
    dp[i][j] = max(dp[i - 1][j],  dp[i] [j - volume[i]] + value[i])
    压缩：
    遍历背包时正向推，用新数据
    dp[j] = max(dp[j],dp[j-w[i]]+c[i])
    """
    dp = [0] * (1 + n)  # dp矩阵 注意维数都+1
    # 遍历物品
    for i in range(m):
        # 遍历背包容量  从后往前
        for j in range(volume[i], n + 1):
            # if j >= volume[i]:
            dp[j] = max(dp[j], dp[j - volume[i]] + value[i])
        print(dp)
    return dp[n]


if __name__ == '__main__':
    print(package(4, 10, [2, 3, 4, 7], [1, 3, 5, 9]))
